The present invention relates to ad-hoc networks. More particularly, the present invention relates to routing in ad-hoc networks.
Conventional networking protocols are based on the characteristics and/or features of fixed networks. In fixed networks, the network configuration typically does not change. Although nodes can be added and removed in fixed networks, the route traveled by data packets between two nodes typically does not change. The disadvantage is that fixed networks cannot be easily reconfigured to account for increases in data traffic, also called system loading. Accordingly, when system loading increases for one node, the surrounding nodes are likely to experience increased delays in the transmission and reception of data.
In contrast to fixed networks, ad-hoc networks are dynamic. An ad-hoc network is formed when a number of nodes decide to join together to form a network. Since nodes in ad-hoc networks operate as both hosts and routers, ad-hoc networks do not require the infrastructure required by fixed networks. Accordingly, ad-hoc networking protocols are based upon the assumption that nodes may not always be located at the same physical location.
Bluetooth is an exemplary ad-hoc networking technology. Bluetooth is an open specification for wireless communication of both voice and data. It is based on a short-range, universal radio link, and it provides a mechanism to form small ad-hoc groupings of connected devices, without a fixed network infrastructure, including such devices as printers, PDAs, desktop computers, FAX machines, keyboards, joysticks, telephones or virtually any digital device. Bluetooth operates in the unlicenced 2.4 GHz Industrial-Scientific-Medical (ISM) band.
FIG. 1 illustrates a Bluetooth piconet. A piconet is a collection of digital devices, such as any of those mentioned above, connected using Bluetooth technology in an ad-hoc fashion. A piconet is initially formed with two connected devices, herein referred to as Bluetooth devices. A piconet can include up to eight Bluetooth devices. In each piconet, for example piconet 100, there exists one master Bluetooth unit and one or more slave Bluetooth units. In FIG. 1 Bluetooth unit 101 is a master unit and unit 102 is a Bluetooth slave unit.
According to Bluetooth technology a slave unit can only communicate directly with a master unit. FIG. 2 illustrates a piconet with a master unit 201 and a plurality of slave units 202-208 arranged in a star network topology. If slave unit 202 wishes to communicate with slave unit 206, slave unit 202 would have to transmit the information it wished to communicate to master unit 201. Master unit 201 would then transmits the information to slave unit 206.
A scatternet is formed by multiple independent and unsynchronized piconets. FIG. 3 illustrates an exemplary scatternet 300. In FIG. 3, piconet 1 includes a master node 303 and the slave nodes 301, 302 and 304; piconet 2 includes the master node 305 and the slave nodes 304, 306, 307 and 308; and piconet 3 includes the master node 309 and the slave nodes 308, 310 and 311. To implement a scatternet it is necessary to use nodes which are members of more than one piconet. Such nodes are herein referred to as forwarding nodes. If, for example, node 301 wishes to communicate with node 310, then nodes 304 and 308 might act as forwarding nodes by forwarding the connection between the two piconets and in particular between nodes 301 and 310. For example, node 301 transfers the information to the master node of piconet 1 node 303. Master node 303 transmits the information to forwarding node 304. Forwarding node 304 then forwards the information to master node 305, which in turn, transmits the information to forwarding node 308. Forwarding node 308 forwards the information to master node 309 which transmits the information to the destination node 310.
FIG. 4a illustrates the protocol layers of two conventional Bluetooth units. As indicated, both units 401 and 402 includes a high level protocol or application 411. They also include a network layer 421, a data link layer including a logical link control and adaptation protocol (L2CAP) 441 and link manager protocol (LMP), and the physical layer including a baseband component.
In general, the protocols which govern the formation and/or updating of routes in an ad-hoc network may be classified as either proactive or reactive. Proactive routing protocols attempt to update and maintain routes between nodes, including routes which are not currently in use. Typically, proactive routing protocols react to network topology changes, even if there is no current traffic which is affected by the topology change. To update and maintain the routes between nodes in an ad-hoc network employing proactive routing, each node periodically transmits control information to other nodes in the network. However, this requires a large amount of signaling, which consumes precious bandwidth and leads to network congestion. The network congestion, in turn, results in greater transmission delays for packets traveling through the network.
In contrast to proactive routing protocols, reactive routing protocols establish routes only when there is an immediate need to transmit packets. Moreover, reactive routing protocols only maintain information about routes which are currently being used for transmitting data packets. Accordingly, reactive protocols result in less network signaling, and hence, less network congestion and less delay due to the congestion as compared to proactive routing protocols.
FIG. 5 illustrates conventional routing techniques. In step 505 the source node generates a message. In step 510 the node determines whether the message is a broadcast message or a unicast message. If the message is a broadcast message, in accordance with the xe2x80x9cBroadcastxe2x80x9d path out of decision step 510, then the source node broadcasts the packets to its neighbor nodes.
If the message is a unicast message, in accordance with the xe2x80x9cUnicastxe2x80x9d path out of decision step 510, then it is determined whether the source node knows a route to the destination node in accordance with step 520. If a route to the destination node is known, in accordance with the xe2x80x9cYesxe2x80x9d path out of decision step 520, the source node will send the unicast message to the node specified in the source node""s routing table in accordance with step 525.
If a route to the destination node is not known, in accordance with the xe2x80x9cNoxe2x80x9d path out of decision step 520, then the source node broadcasts a request for route message in accordance with step 530. In step 535 a neighbor node receives the request for route message. In step 540 the neighbor node determines whether it has already processed the request for route message. The neighbor node makes this determination based upon a source node address and broadcast identifier in the request for route message. If the neighbor node has already processed the request for route message, in accordance with the xe2x80x9cYesxe2x80x9d path out of decision step 540, the node will drop the message in accordance with step 545.
If the node has not already processed the message, in accordance with the xe2x80x9cNoxe2x80x9d path out of decision step 540, then the node stores the source node address and broadcast identifier. In step 555 the node rebroadcasts the request for route message to its neighbor nodes. In step 560 the node determines whether it is the destination node. If the node determines that it is not the destination node, in accordance with the xe2x80x9cNoxe2x80x9d path out of decision step 560, then the node is done with its processing for this message. However, if the node is the destination node, in accordance with the xe2x80x9cYesxe2x80x9d path out of decision step 560, the node will send a response back to the source node in accordance with step 565. In step 570 the source node sends the unicast message to the destination node over the newly established route. In accordance with reactive routing, the source node will only request a new route when the actual route being used is broken.
In conventional networks there are typically two types of broadcast messages. The first type of broadcast message are messages which the source node sends to spread information to other nodes in the network. When this type of broadcast message is sent the source does not expect to receive a reply message. The second type of broadcast message are messages which the source node expects to receive a reply message from one or more network nodes.
Since ad-hoc networks are dynamic, nodes may change their location in the network. When the node changes its location, the node may not have the same address as the node had at its prior location. In order to transmit data from a source node to a destination node the source node may first obtain its own network address, resolve the name of the destination, obtain the hardware address of the destination node and determine a route to the destination node. However, since conventional ad-hoc routing protocols are based on the characteristics and/or features associated with fixed networks, the conventional ad-hoc routing protocols assume that the source node and destination node hardware addresses are known.
One exemplary networking protocol is Internet Protocol (IP). In IP there are several different broadcast messages that a source node generates where the source node expects a reply from one or more node(s) in the network. In IP three exemplary types of broadcast messages where the source expects a reply are dynamic host configuration protocol (DHCP), name resolution and address resolution protocol. DHCP is concerned with dynamic allocation of IP addresses to nodes. Name resolution is used to obtain the IP address when the name of the node. ARP is used when the logical address of the node is known, e.g., the IP address, but the hardware address, e.g., the Ethernet address of the node is not known.
Accordingly, in an ad-hoc network the source node may have to perform a separate broadcast for DHCP, name resolution or ARP, and route discovery before the source node can begin to transmit data to the destination node. These separate broadcasts result in delay in sending the information from the source node to the destination node. Sending these separate broadcasts also adds to the load of the network.
Accordingly, it would be desirable to minimize the number of broadcast messages required for setting up a route from a source node to a destination node when employing reactive protocols in an ad-hoc network.
These and other problems, drawbacks and limitations of conventional techniques are overcome according to the present invention by placing a broadcast message which the source expects a reply message in a broadcast message for route discovery. The combined message is broadcast throughout the ad-hoc network. When the combined broadcast message is received at the destination node, the destination node generates a response message including a reply message to the broadcast message that the source node expects a reply. The response message is sent back to the source node over the route which the combined broadcast message traveled to the destination node.
Accordingly, it is an objective of the present invention to minimize the amount of broadcasts required for setting up a route in an ad-hoc network.
It is another objective of the present invention to minimize the load on the network when setting up a route in an ad-hoc network by placing a broadcast message which the source node expects a reply message in a broadcast message which determines a route to the node which generates the reply message.
It is also an objective of the present invention to lower the delay at the source node by speeding up the signaling required to set up a route between a source and destination node.
In accordance with one aspect of the present invention, the foregoing and other objects are achieved by a method and/or an apparatus for determining a route from a source node to a destination node, wherein a request for route broadcast message is used to discover and establish routes between the source node and destination node. The source node generates a broadcast message for which the source node expects a reply message. The broadcast message is placed in a request for route broadcast message. The source node then broadcasts the request for route broadcast message to neighboring nodes.
In each of the neighboring nodes it is determined whether the particular neighboring node is the node which generates a reply message. If the particular node is the node which generates a reply message then a response message to the request for route broadcast message is generated. The response message is sent to the source node over the temporary route stored in each neighboring node in a path between the source node and the node which generated the reply message. As the response message is sent from the node which generate the reply message to the source node a route is activated in each of the neighboring nodes in the route between the source node and the destination node.
In accordance with yet another aspect of the present invention, the foregoing and other objects are achieved by a method and/or an apparatus for determining a route from a source node to another node, wherein all nodes in the network include a network adaptation layer and a higher layer. In the higher layer of the source node a broadcast message for which the source node expects a reply message is generated. The message for which the source node expects a reply message is placed in a network adaptation layer request for route broadcast message. The network adaptation layer request for route broadcast message is broadcast from the source node to neighboring nodes.